# Blackley scheme

Перед нами схема разделения `секрета Блэкли (2, 2)`, то есть разделили секрет на две части и только двое его смогут восстановить. Схема для разделения на две части построена по следующему образу:
Выбираем простое число p и определяем координаты секретной точки `(x_0,y_0)`, которую зададим в виде пересечения двух прямых. Для этого выбирают случайные числа a, b. И подстраивают так, чтобы эта прямая проходила через точку `(x_0,y_0)`. Таким образом у нас два уравнения прямой, и если соединить два ключа, то по пересечению однозначно находим эту точку, Имея один ключ, сможем найти только прямую на которой эта точка лежит.
Однако можно заметить, что `(x_0,y_0)` это маленькие числа по сравнению с `a, b, z и p`. А какой алгоритм применяется если у нас есть относительно малые числа. Правильно `LLL-алгоритм (алгоритм Ленстры-Ленстры-Ловаса).`
Для начала разберёмся, что такое решётка. 
>Решётка — это аналог векторного пространства, за тем исключением, что в векторном пространстве вектора умножаются на любое число, а в решётке только на целое, таким образом вместо всего пространства мы получаем только множество точек составленные из всевозможных комбинаций базисных векторов. 

Так вот `LLL-алгоритм` позволяет перейти к другому базису решётки. Отличительная особенность данного базиса заключается в том, что первый вектор – это вектор наименьшей длины. Таким образом при грамотном использовании данного алгоритма можно найти крайне маленькие числа по сравнению с большими.
У нас можно как раз построить решётку из векторов `(1,0,0,a); (0,1,0,b); (0,0,1,z); (0,0,0,p)`. На основе этих векторов можно получить вектор `(x,y,-1,0)=x(1,0,0,a)+ y(0,1,0,b)-(0,0,1,z)+k(0,0,0,p)`.Так как `x и y` малые по сравнению с остальными числами, то вектор `(x,y,-1,0)` является вектором наименьшей длины в этой решётке и его найдёт `LLL-алгоритм`. 
`LLL-алгоритм` уже встроен и хорошо реализован в `SageMath` – это математическая оболочка над `Python`, которой часто пользуются в криптографии. Так что пример кода реализован на `Sage`:

```python
a = 1061547…672160117388932468883974754447565038803
b = 2703732…811303604354387806362047265903872735816
z = 1975111…943570415001425184760166309113621673603
p = 1989538…225764072181862514388986295451797998529

def main():
    A = Matrix([[1, 0, 0, a], 
                [0, 1, 0, b], 
                [0, 0, 1, z], 
                [0, 0, 0, p]])  
    res = [abs(i) for i in A.LLL()[0]]
    x, y = res[0], res[1]
    len_x = (int(x).bit_length() + 7) // 8
    flagx = int(x).to_bytes(len_x, byteorder = 'big')
    len_y = (int(y).bit_length() + 7) // 8
    flagy = int(y).to_bytes(len_y, byteorder = 'big')
    print(flagx + flagy)

if __name__ == "__main__":
    main()
```

Найдя `x и y`, переводим их в байты и конкатенируем, получаем флаг.

**Ответ:** RDGCTF{LLL_alg0r1thm_1s_f0r3v3r_1n_my_h3art}
